package KMP算法_字符串匹配;

import java.util.Arrays;

public class KMPMatch {
    public static void main(String[] args) {
        String s1 = "BBC ABCDAB ABCDABCDABDE";
        String s2 = "ABCDABD";

        int[] kt = getKT("ABCDABD");
        int kmp = KMP(s1, s2, kt);
        System.out.println(kmp);
    }
    // 获取子串字符串的部分匹配表
    public static int[] getKT(String dest){
        // 创建一个next数组,保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0;// 如果字符串的长度为一,部分匹配值就是零
        for(int i = 1,j = 0;i < dest.length();i++){
            while(j > 0 && dest.charAt(i) != dest.charAt(j)){
                j = next[j - 1];
            }
            if(dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }


    public static int KMP(String s1,String s2,int[] next){
        for(int i = 0,j = 0;i<s1.length();i++){
            if(s1.charAt(i) == s2.charAt(j)){
                j++;
            }else{
                i = i + next[j] -1;
                j = 0;
            }
            if(j == s2.length()){
                return i-j+1;
            }
        }
        return -1;
    }
}
